package codeRandomThoughts.Test235二叉搜索树的最近公共祖先;

import codeRandomThoughts.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 递归法
 */
public class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return root;
        List<TreeNode> pPath = getPathFromTarget(p, root);
        List<TreeNode> qPath = getPathFromTarget(q, root);

        if (pPath.size() > qPath.size()) {
            List<TreeNode> tem = pPath;
            pPath = qPath;
            qPath = tem;
        }

        for (int i = 0; i < pPath.size(); i++) {
            if (pPath.get(i) != qPath.get(i)) {
                return pPath.get(i - 1);
            }
        }
        return pPath.get(pPath.size() - 1);
    }

    public List<TreeNode> getPathFromTarget(TreeNode target, TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        int val = target.val;
        while (root.val != val) {
            if (val > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
            list.add(root);
        }
        return list;
    }
}
